1. Field of the Invention
This invention relates generally to distributed computing, and more particularly to systems and methods for tracking the locations of distributed computations and/or data for a subdivided iteration space.
2. Description of the Related Art
Parallel programming has traditionally involved a tradeoff between two competing factors: the desire to express the solution to a scientific problem as simply and naturally as possible, and the need to effectively utilize the large computational resources required to obtain a solution. For the foreseeable future, the cost of communication in a large parallel machine will continue to be a limiting factor for performance. This dichotomy, then, may be viewed as a tradeoff in program structure. In other words, in some cases, a program may be structured around its communication. For example, it may be structured via explicit message passing using the Message Passing Interface (MPI) standard. In other cases, a problem may be expressed as naturally as possible with the hope of obtaining a reasonably efficient code that is adaptable and easily maintained.
Physical simulations, the stock-in-trade of parallel computing, often focus on propagating phenomena (matter, force, energy) through space. Arrays of floating-point numbers are common currency for such spatial simulation. These arrays must be carved up, either explicitly or implicitly, into pieces that can be distributed across a machine. Similarly, computations on these arrays must be carved up into pieces suitable for executing in parallel.
Individual processors are becoming parallel machines in miniature. This combined with the increasing size of large parallel machines means that parallel computing systems will have to expose, and load balance, several orders of magnitude more computation than currently available parallel machines. However, even current approaches often fail, as evidenced by the low utilizations of most large parallel machines.